package day01;

public class MyLinkedList<E> {
    private static class Node<E>{
        E item;
        Node<E> prev;
        Node<E> next;
        Node(E e){
            item = e;
        }
    }
    private int size;
    private Node<E> first;
    private Node<E> last;
    public boolean add(E e){
        Node<E> node = new Node<>(e);
        if (size==0) {
            first = node;
            last = node;
        }else{
            node.prev = last;
            last.next = node;
            last = node;
        }
        size++;
        return true;
    }

    public boolean add(int index, E e){
        if (index<0 || index>size){
            throw new IndexOutOfBoundsException("越界"+index);
        }
        if (index == size){
            return add(e);
        }
        //单独处理头节点
        if (index == 0){
            Node<E> node = new Node<>(e);
            node.next = first;
            first.prev = node;
            first = node;
            size++;
            return true;
        }
        Node<E> node = seekNode(index);
        Node<E> next = node;
        Node<E> prev = node.prev;
        node = new Node<>(e);
        prev.next = node;
        node.next = next;
        next.prev = node;
        node.prev = prev;
        size++;
        return true;
    }

    private Node<E> seekNode(int index) {
        Node<E> node;
        if (index < size >> 1) {
            node = first;
            for(int i = 0; i != index; i++){
                node = node.next;
            }
        } else {
            node = last;
            for (int i = size - 1; i != index; i--) {
                node = node.prev;
            }
        }
        return node;
    }

    public E get(int index){
        Node<E> node = seekNode(index);
        return node.item;
    }
    public void reverse(){
        if (size == 0 || size == 1){
            return;
        }
        //从最后一个节点开始处理
        Node<E> node = last;
        //第一个节点单独处理
        Node<E> n = node;
        node = node.prev;
        first = n;
        last = n;
        n.prev=null;
        n.next=null;
        //每次把节点插入到最后位置
        for (int i=1; i<size; i++){
            n = node; //每次取出最后一个节点
            node = node.prev;
            last.next = n;
            n.prev = last;
            n.next = null;
            last = n;
        }
    }
    public int size(){
        return size;
    }
    public E remove(int index){
        if (index <0 || index >= size){
            throw new IndexOutOfBoundsException("越界");
        }
        if (size == 1){
            Node<E> node = first;
            first = null;
            last = null;
            size = 0;
            return node.item;
        }
        if (index == 0){
            Node<E> node = first;
            first = node.next;
            first.prev = null;
            node.next = null;
            size--;
            return node.item;
        }
        if (index == size-1){
            Node<E> node = last;
            last = node.prev;
            last.next = null;
            node.prev = null;
            size--;
            return node.item;
        }
        Node<E> node = seekNode(index);
        Node<E> next = node.next;
        Node<E> prev = node.prev;
        next.prev = prev;
        prev.next = next;
        node.next = null;
        node.prev = null;
        size--;
        return node.item;
    }
    public String toString(){
        if (size == 0){
            return "[]";
        }
        StringBuilder builder = new StringBuilder("[")
                .append(first.item);
        Node<E> node = first.next;
        for (int i=1; i<size; i++){
            builder.append(", ").append(node.item);
            node = node.next;
        }
        return builder.append("]").toString();
    }
}



